class Solution {
public:
    int countMaxOrSubsets(vector<int>& nums) {
        int n = nums.size();
        int mask = 1 << n;
        vector<int> dp(mask);
        int Max = 0;
        
        // for(int state = 0;state < mask;state++){
        //     int ns = state;
        //     for(int i = 0;i < n;i++){
        //         if(((ns>>i) & 1) == 0){
        //             dp[ns|(1<<i)] = max(dp[ns|(1<<i)],dp[ns]|nums[i]);
        //             Max = max(Max,dp[ns|(1<<i)]);
        //         }
        //     }
        // }
        
        unordered_map<int,int> hash;
        for(int i = 0;i < n;i++){
            hash[1<<i] = i;
        }
        
        for(int state = 1;state < mask;state++){
            int lowbit = state & -state;
            int os = state - lowbit;
            int idx = hash[lowbit];
            
            dp[state] = dp[os] | nums[idx];
            Max = max(Max,dp[state]);
        }
        
        int ans = 0;
        for(int state = 1;state < mask;state++){
            if(dp[state] == Max){
                ans++;
            }
        }
        return ans;
    }
};
